#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode {
    int val;
    struct ListNode* next;

};
struct ListNode* reverseList(struct ListNode* head)
{
    if (head == NULL)
    {
        return NULL;
    }
    struct ListNode* prev = NULL;
    struct ListNode* curr = head;
    while (curr)
    {
        struct ListNode* tmp = prev;
        prev = curr;
        curr = curr->next;
        prev->next = tmp;

    }
    return prev;

}
struct ListNode* removeElements(struct ListNode* head, int val)
{
    struct ListNode* cur = head;
    struct ListNode* prev = NULL;
    if (head == NULL)
    {
        return NULL;
    }
    while (cur)
    {
        if (cur->val == val)
        {
            if (cur == head)
            {
                head = cur->next;
                free(cur);
                cur = head;

            }
            else
            {
                prev->next = cur->next;
                free(cur);
                cur = prev->next;

            }
        }
        else
        {
            prev = cur;
            cur = cur->next;

        }
        


    }
    return head;
}
struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k)
{
    struct ListNode* front = pListHead;
    struct ListNode*back= pListHead;
    while (k--)
    {
        front = front->next;
        if (front == NULL)
        {
            return NULL;
        }
    }
    while (front)
    {
        back = back->next;
        front = front->next;
    }
    return back;

}
struct ListNode* CreatNode(x)
{
    struct ListNode* tmp = (struct ListNode*)malloc(sizeof(struct ListNode));
    tmp->val = x;
    tmp->next = NULL;
    return tmp;

}
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    struct ListNode* phead = NULL;
    struct ListNode* tail = NULL;
    while (list1 && list2)
    {
        if (list1->val <= list2->val)
        {
            if (phead == NULL)
            {
                phead = CreatNode(list1->val);
                tail = phead;
            }
            else
            {
                tail->next = CreatNode(list1->val);
                tail = tail->next;
               
            }
            
            list1 = list1->next;
        }
        else
        {
            if (phead == NULL)
            {
                phead = CreatNode(list2->val);
                tail = phead;
            }
            else
            {
                tail->next = CreatNode(list2->val);
                tail = tail->next;
            }
            list2 = list2->next;
        }
    }
    if (list2)
    {
        if (phead == NULL)
        {
            phead = list2;
            
        }
        else
        {
            tail->next = list2;
        }
    }
    if (list1)
    {
        if (phead == NULL)
        {
            phead = list1;

        }
        else
        {
            tail->next = list1;
        }
    }
    return phead;
}
int main()
{
    struct ListNode* n1 = NULL;/*(struct ListNode*)malloc(sizeof(struct ListNode));*/
	struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* n5 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* n6 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* n7 = (struct ListNode*)malloc(sizeof(struct ListNode));
	/*n1->val = 1;
    n2->val = 2;n3->val = 3;n4->val = 4;*/n5->val = 5;n6->val = 6;n7->val = 7;
	/*n1->next = n2;n2->next = n3;n3->next = n4;n4->next = NULL;*/n5->next = n6;
    n6->next = n7;n7->next = NULL;
    //struct ListNode* ret = removeElements(n1, 6);
    struct ListNode* ret = mergeTwoLists(n1,n5 );
    assert(ret);
    while (ret)
    {
        printf("%d ", ret->val);
        ret=ret->next;
    }
    /*struct ListNode* ret = FindKthToTail(n1, 8);
    
    printf("%d", ret->val);*/
	return 0;
}